Min-Cut Theorem

释义 Definition

最小割定理：在流网络中，最大流的值等于最小割的容量。它与“最大流最小割定理（Max-Flow Min-Cut Theorem）”同义，常用于证明最大流算法的正确性、分析网络瓶颈与连通性。（在不同语境下也可能简称为“最小割相关定理”，但最常见指的就是最大流=最小割。）

发音 Pronunciation (IPA)

/ˌmɪn ˈkʌt ˈθiːərəm/

例句 Examples

The min-cut theorem helps us find the bottleneck in a network.
最小割定理帮助我们找出网络中的瓶颈。

Using the min-cut theorem, we can prove that the algorithm’s max flow is optimal by showing it equals the capacity of a minimum s–t cut.
利用最小割定理，我们可以通过证明算法得到的最大流等于某个最小的 s–t 割的容量，从而证明该最大流是最优的。

词源 Etymology

min-cut 来自 minimum cut（最小割）：在图论/网络流中，“cut（割）”指把顶点集合分成两部分（常见为把源点 s 与汇点 t 分开）的分割；“minimum（最小）”表示在所有这类分割中，跨越两部分的边容量之和最小。theorem（定理）源自希腊语 theōrēma，指可被证明的结论。合起来即“关于最小割的定理”，通常特指“最大流=最小割”的经典结论。

相关词 Related Words

• Maximum
• Flow
• Cut
• Capacity
• Residual
• Augmenting Path
• Source
• Sink
• Bottleneck
• Duality

文学与著作中的用例 Literary Works

• “Maximal Flow Through a Network”（Ford & Fulkerson，1956）：提出并奠定最大流—最小割理论基础的经典论文，系统讨论该定理与算法思想。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：网络流章节讲解最大流最小割定理，并用于证明 Ford–Fulkerson、Edmonds–Karp 等算法性质。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：以工程与算法视角全面覆盖网络流问题，频繁使用最小割定理作为核心工具。
• Combinatorial Optimization: Polyhedra and Efficiency（Schrijver）：从组合优化与多面体角度讨论割、流与对偶性，包含该定理在更一般框架下的表达。